맨위로가기

힙 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

힙 정렬은 배열을 이진 최대 힙으로 구성하여 정렬하는 알고리즘이다. 힙의 루트 노드와 마지막 요소를 교환하고, 힙을 재구성하는 과정을 반복하여 정렬을 수행하며, 시간 복잡도는 O(n log n)이다. 퀵 정렬과 경쟁하는 효율적인 정렬 알고리즘으로, 코드 단순성과 O(n log n) 시간 복잡도 보장, 그리고 실시간 컴퓨팅 및 임베디드 시스템에 적합하다는 장점이 있다. 힙 정렬의 변형 알고리즘으로는 비교 횟수를 줄인 바텀업 힙 정렬, 삼항 힙 정렬 등이 있으며, 퀵 정렬에 비해 참조 지역성이 낮다는 단점이 있다.

더 읽어볼만한 페이지

  • 힙 - 힙 (자료 구조)
    힙은 이진 트리 기반의 자료구조로, 부모 노드의 키 값이 자식 노드보다 크거나 작도록 구성되며, 최대 힙과 최소 힙이 존재하고, 배열로 구현되어 삽입, 삭제 연산의 시간 복잡도는 O(log n)이며, 다양한 분야에 활용된다.
  • 힙 - 이진 힙
    이진 힙은 완전 이진 트리 기반 자료 구조로 우선순위 큐 구현에 사용되며, 힙 속성을 유지하기 위해 삽입/제거 시 상향 또는 하향 힙 연산을 수행하고 배열로 효율적인 구현이 가능하다.
  • 비교 정렬 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 비교 정렬 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
  • 정렬 알고리즘 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 정렬 알고리즘 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
힙 정렬
개요
힙 정렬 실행 모습
힙 정렬 알고리즘이 임의의 숫자 열에 대해 작동하는 예시. 알고리즘의 첫 번째 단계에서는 배열의 요소를 이진 힙 조건을 만족하도록 정렬함. 그 후 실제로 정렬된 위치에 다시 정렬하기 전에 힙 구조가 그림 위에 나타남.
분류정렬 알고리즘
자료 구조배열
성능
시간 복잡도O(n log n)
평균 시간 복잡도O(n log n)
최선 시간 복잡도O(n)
공간 복잡도O(1) (제자리 정렬)
기타
고안자J. W. J. 윌리엄스
발표 년도1964년

2. 알고리즘

힙 정렬 알고리즘은 크게 두 단계로 나뉜다.

1. n개의 노드로 구성된 완전 이진 트리를 만든다. 루트 노드부터 시작하여 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 구성한다.

2. 최대 힙을 구성한다. 최대 힙은 부모 노드가 자식 노드보다 큰 트리를 의미한다. 단말 노드(leaf node)를 자식 노드로 가지는 부모 노드부터 시작하여 아래에서 루트까지 올라가며 순차적으로 힙을 만든다.

3. 가장 큰 수(루트 노드)를 가장 작은 수와 교환한다.

4. 2번과 3번을 반복한다.

힙 정렬은 일반적으로 제자리에서 수행된다. 배열은 정렬되지 않은 부분과 힙으로 정렬된 부분(처음에는 비어 있음)으로 나뉜다. 각 단계는 정렬되지 않은 부분을 줄이고 힙으로 정렬된 부분을 늘린다. 정렬되지 않은 부분이 비어 있으면 이 단계가 완료된다.

모든 데이터를 힙 구조에 등록하고 나면, 힙에서 데이터를 꺼내는 단계로 넘어간다. 힙의 루트를 꺼내 배열의 뒤에서부터 채워나간다. m을 N에서 1까지 줄여가면서, 꺼낸 루트 요소를 배열의 첨자 m에 둔다. 즉, (N - m)개의 데이터를 꺼낸 상태에서는 첨자 1 ~ m이 힙 구조이며, m + 1 ~ N이 정렬된 리스트가 된다.

모든 데이터를 힙 구조에서 꺼내고 나면, 배열 전체가 정렬된 상태가 된다.

2. 1. 힙 구성

힙은 암시적 자료 구조로, 정렬할 객체의 배열 외에 추가 공간을 사용하지 않는다. 배열은 완전 이진 트리로 해석되며, 각 노드의 부모 및 자식 링크는 배열 인덱스에 대한 간단한 산술 연산으로 정의된다. 0부터 시작하는 배열의 경우, 루트 노드는 인덱스 0에 저장되며, 노드 i에 연결된 노드는 다음과 같다.

```

iLeftChild(i) = 2⋅i + 1

iRightChild(i) = 2⋅i + 2

iParent(i) = floor((i−1) / 2)

```

여기서 바닥 함수는 이전 정수로 내림한다.

이진 트리는 각 노드가 두 자식 이상인 경우 최대 힙이다. 또는 각 노드는 부모보다 작거나 같다. 이 규칙을 트리 전체에 적용하면 최대 노드가 트리의 루트에 위치하게 된다. 힙 정렬 알고리즘의 첫 번째 단계에서는 주어진 데이터를 힙으로 구성한다.

윌리엄스의 힙 구성 알고리즘을 사용한 힙 정렬의 예


힙정렬되지 않음요소 교환
65, 3, 1, 8, 7, 2, 4
6, 53, 1, 8, 7, 2, 4
6, 5, 31, 8, 7, 2, 4
6, 5, 3, 18, 7, 2, 4
6, 5, 3, 1, 87, 2, 45 ↔ 8
6, 8, 3, 1, 57, 2, 46 ↔ 8
8, 6, 3, 1, 57, 2, 4
8, 6, 3, 1, 5, 72, 43 ↔ 7
8, 6, 7, 1, 5, 32, 4
8, 6, 7, 1, 5, 3, 24
8, 6, 7, 1, 5, 3, 2, 41 ↔ 4
8, 6, 7, 4, 5, 3, 2, 1



힙 구조는 데이터 자체의 정렬 순서(배열)만으로 표현할 수 있으며, 포인터 등의 제어용 데이터가 필요 없다. 힙 정렬을 구현할 때는 이러한 장점을 살려, 원래의 데이터 영역을 그대로 힙 구조나 정렬된 리스트로 전용하는 인플레이스 정렬로 구현하는 경우가 많다.

먼저 각 데이터를 힙 구조에 등록한다. m개의 데이터를 처리한 상태에서는, 첨자 1 ~ m이 힙 구조이고, (m + 1) ~ N이 미정렬 리스트가 된다. m + 1번째 데이터를 꺼내 힙 구조에 등록한다. 이때 구성하는 힙은, 오름차순으로 정렬할 경우에는 루트가 최대값이 되도록, 내림차순으로 정렬할 경우에는 루트가 최소값이 되도록 구성한다.

2. 2. 힙 추출

힙의 루트(최대값 또는 최소값)를 배열의 마지막 요소와 교환하고, 힙의 크기를 줄인다. 손상된 힙을 복구하기 위해 `siftDown`(또는 `heapify`) 함수를 호출하여 새로운 루트 요소를 힙의 올바른 위치로 이동시킨다. 힙에 하나의 요소만 남을 때까지 이 과정을 반복한다.[9]

힙 추출 단계는 다음의 순서로 진행된다.

1. 배열에 `heapify()` 함수를 호출한다. 이는 *O*(*n*) 연산으로 배열에서 힙을 구성한다.

2. 배열의 첫 번째 요소(힙에서 가장 큰 요소)를 힙의 마지막 요소와 교환한다. 힙의 고려 범위를 하나 줄인다.

3. 배열에 `siftDown()` 함수를 호출하여 새로운 첫 번째 요소를 힙의 올바른 위치로 이동시킨다.

4. 나머지 배열이 단일 요소가 될 때까지 (2)단계로 돌아간다.

`heapify()` 연산은 한 번 실행되며 성능은 *O*(*n*)이다. `siftDown()` 함수는 *n*번 호출되며, 루트 노드에서 시작하는 순회로 인해 매번 *O*(log *n*) 작업이 필요하다. 따라서 이 알고리즘의 성능은 *O*(*n* + *n* log *n*) = *O*(*n* log *n*)이다.

알고리즘의 핵심은 `siftDown()` 함수이다. 이 함수는 더 작은 힙에서 이진 힙을 구성하며, 두 가지 동등한 방식으로 생각할 수 있다.

  • 두 개의 이진 힙과 두 힙에 속하지 않은 공유된 부모 노드가 주어지면 이를 단일의 더 큰 이진 힙으로 병합한다.
  • 최대 힙 속성(자식이 부모보다 크지 않음)이 루트 노드와 자식 사이를 제외한 모든 곳에서 유지되는 "손상된" 이진 힙이 주어지면, 손상되지 않은 힙을 생성하도록 복구한다.


루트에서 최대 힙 속성을 설정하려면 최대 세 개의 노드(루트와 두 자식)를 비교해야 하며, 가장 큰 노드를 루트로 만들어야 한다. 이는 가장 큰 자식을 찾은 다음 해당 자식을 루트와 비교하여 가장 쉽게 수행할 수 있다. 세 가지 경우가 있다.

1. 자식이 없는 경우(두 원래 힙이 비어 있는 경우), 힙 속성이 자명하게 유지되므로 추가 작업이 필요하지 않다.

2. 루트가 가장 큰 자식보다 크거나 같은 경우, 힙 속성이 유지되므로 마찬가지로 추가 작업이 필요하지 않다.

3. 루트가 가장 큰 자식보다 작은 경우, 두 노드를 교환한다. 힙 속성은 이제 새로 승격된 노드에서 유지되지만(자식보다 크거나 같고, 실제로 모든 후손보다 큼), 새로 강등된 전 루트와 새 자식 사이에서 위반될 수 있다. 이를 수정하려면 새로 강등된 전 루트를 루트로 하는 서브트리에서 `siftDown()` 작업을 반복한다.

어떤 `siftDown()` 호출에서든 반복 횟수는 트리의 높이로 제한되며, 이는 *O*(log *n*)이다.

2. 3. 시간 복잡도

일반적으로 힙 정렬은 O(n \log n)의 시간 복잡도를 가진다. 힙 정렬은 배열을 이진 최대 힙으로 재배열하는 것으로 시작한다. 이 과정은 트리의 깊이 만큼 이루어지므로 O(\log n)의 수행 시간이 걸린다.

알고리즘의 단계는 다음과 같다.

1. 배열에 `heapify()` 함수를 호출한다. 이는 O(n) 연산으로 배열에서 힙을 구성한다.

2. 배열의 첫 번째 요소(힙에서 가장 큰 요소)를 힙의 마지막 요소와 교환한다. 힙의 고려 범위를 하나 줄인다.

3. 배열에 `siftDown()` 함수를 호출하여 새로운 첫 번째 요소를 힙의 올바른 위치로 이동시킨다.

4. 나머지 배열이 단일 요소가 될 때까지 (2)단계로 돌아간다.

`heapify()` 연산은 한 번 실행되며 성능은 O(n)이다. `siftDown()` 함수는 n번 호출되며, 루트 노드에서 시작하는 순회로 인해 매번 O(\log n) 작업이 필요하다. 따라서 이 알고리즘의 성능은 O(n + n \log n) = O(n \log n)이다.

`siftDown()` 함수는 다음과 같은 두 가지 방식으로 생각할 수 있다.

  • 두 개의 이진 힙과 두 힙에 속하지 않은 공유된 부모 노드가 주어지면 이를 단일의 더 큰 이진 힙으로 병합한다.
  • 최대 힙 속성(자식이 부모보다 크지 않음)이 루트 노드와 자식 사이를 제외한 모든 곳에서 유지되는 "손상된" 이진 힙이 주어지면, 손상되지 않은 힙을 생성하도록 복구한다.


어떤 `siftDown()` 호출에서든 반복 횟수는 트리의 높이로 제한되며, 이는 O(\log n)이다.

3. 구현 예시

힙 정렬 알고리즘은 배열을 이진 최대 힙으로 재배열한 다음, 힙의 루트(가장 큰 요소)를 마지막 요소와 교환하고 힙의 크기를 줄이는 과정을 반복하여 정렬을 수행한다.[1]

주요 단계는 다음과 같다.[1]

1. 배열에 `heapify()` 함수를 호출하여 힙을 구성한다. ( 연산)

2. 힙의 첫 번째 요소(가장 큰 요소)를 마지막 요소와 교환하고, 힙의 크기를 1 줄인다.

3. `siftDown()` 함수를 호출하여 새로운 첫 번째 요소를 힙의 올바른 위치로 이동시킨다.

4. 힙에 하나의 요소만 남을 때까지 2단계와 3단계를 반복한다.

`heapify()`는 한 번 실행()되며, `siftDown()` 함수는 번 호출()된다. 따라서 전체 알고리즘의 성능은 이다.[1]

`siftDown()` 함수는 루트 노드와 그 자식 노드들을 비교하여 최대 힙 속성을 설정한다. 최대 세 개의 노드를 비교하며, 가장 큰 노드를 루트로 만든다. 다음과 같은 세 가지 경우가 있을 수 있다.[1]


  • 자식이 없는 경우: 추가 작업이 필요하지 않다.
  • 루트가 가장 큰 자식보다 크거나 같은 경우: 추가 작업이 필요하지 않다.
  • 루트가 가장 큰 자식보다 작은 경우: 두 노드를 교환하고, 새로 강등된 루트를 기준으로 `siftDown()` 작업을 반복한다.


`siftDown()` 호출에서 반복 횟수는 트리의 높이()로 제한된다.[1]

3. 1. C

c



static void upheap(double arr[], int n);

static void downheap(double arr[], int n);

static inline void

swap(double arr[], int a, int b)

{

double tmp = arr[a];

arr[a] = arr[b];

arr[b] = tmp;

}

void

heapsort(double arr[], int n_elems)

{

int i = 0;

/*

  • arr의 처음부터 차례로 힙을 성장시킨다.
  • 0 1 2 | 3 4 5
  • [ ] [ ] [ ]|[ ] [ ] [ ]
  • 힙 | 미처리 입력
  • ===>
  • i는 힙 내의 요소 수이자, 미처리 데이터의 선두를 가리키기도 한다.
  • /

/* 배열이 전부 힙으로 교체될 때까지 반복한다. */

while (++i < n_elems) {

/*

  • 배열의 첫 번째 요소를 힙의 마지막으로 이동시키는데, 둘 다
  • 정확히 같은 위치에 처음부터 있으므로 경계를 이동시키기만 하면 된다.
  • /


/*

  • arr[i]에 힙에 새롭게 추가된 데이터가 있는 것으로 간주하고,
  • 처음부터 arr[i]까지가 힙이 되도록 재구성한다.
  • /

upheap(arr, i);

}

/*

  • arr의 끝에서부터 차례로 힙에서 꺼내어 정렬한다.
  • 0 1 2 | 3 4 5
  • [ ] [ ] [ ]|[ ] [ ] [ ]
  • 힙 | 정렬된 배열
  • <===
  • /

/* 힙이 전부 배열로 교체될 때까지 반복한다. */

while (--i > 0) {

/*

  • 힙의 첫 번째 요소를 배열로 이동시키는 동시에 힙의 마지막
  • 요소를 힙의 첫 번째로 이동시키는 swap
  • /

swap(arr, 0, i);

/*

  • arr[0]에 힙의 마지막에서 이동된 데이터가 있는 것으로 간주하고,
  • 처음부터 arr[i - 1]까지가 힙이 되도록 재구성한다.
  • /

downheap(arr, i);

}

}

/*

  • heaptree에 대한 매크로
  • 0 기반 배열용
  • /

#define LEFT_CHILD(i) (((i) + 1) * 2 - 1)

#define RIGHT_CHILD(i) (((i) + 1) * 2)

#define PARENT(i) (((i) + 1) / 2 - 1)

/*

  • arr[n]에 힙에 새롭게 추가된 데이터가 있는 것으로 간주하고,
  • 처음부터 arr[n]까지가 힙이 되도록 재구성한다.
  • /

static void

upheap(double arr[], int n)

{

while (n > 0) {

int m = PARENT(n);

if (arr[m] < arr[n]) {

swap(arr, m, n);

} else {

break;

}

n = m;

}

}

/*

  • arr[0]에 힙의 마지막에서 이동된 데이터가 있는 것으로 간주하고,
  • 처음부터 arr[n - 1]까지가 힙이 되도록 재구성한다.
  • /

static void

downheap(double arr[], int n)

{

int m = 0;

int tmp = 0;

for (;;) {

int l_chld = LEFT_CHILD(m);

int r_chld = RIGHT_CHILD(m);

if (l_chld >= n) {

break;

}

if (arr[l_chld] > arr[tmp]) {

tmp = l_chld;

}

if ((r_chld < n) && (arr[r_chld] > arr[tmp])) {

tmp = r_chld;

}

if (tmp == m) {

break;

}

swap(arr, tmp, m);

m = tmp;

}

}


3. 2. Java

java

public class Heap

{

private int[] element; // element[0]에는 길이가 들어 있다.

private static final int ROOTLOC = 1;

private static final int DEFAULT = 10;

public Heap(int size) {

if(size > DEFAULT) {

element = new int[size + 1];

element[0] = 0;

}

else {

element = new int[DEFAULT + 1];

element[0] = 0;

}

}

public void add(int newnum) {

if(element.length <= element[0] + 1) {

int[] elementTemp = new int[element[0] * 2];

for(int x = 0; x < element[0]; x++) {

elementTemp[x] = element[x];

}

element = elementTemp;

}

element[++element[0]] = newnum;

upheap();

}

public int extractRoot() {

int extracted = element[1];

element[1] = element[element[0]--];

downheap();

return extracted;

}

public void upheap() {

int locmark = element[0];

while(locmark > 1 && element[locmark / 2] > element[locmark]) {

swap(locmark / 2, locmark);

locmark /= 2;

}

}

public void downheap() {

int locmark = 1;

while(locmark * 2 <= element[0])

{

if(locmark * 2 + 1 <= element[0]) {

int small = smaller(locmark * 2, locmark * 2 + 1);

if(element[small] >= element[locmark]) break;

swap(locmark, small);

locmark = small;

}

else {

if(element[locmark * 2] >= element[locmark]) break;

swap(locmark, locmark * 2);

locmark *= 2;

}

}

}

public void swap(int a, int b) {

int temp = element[a];

element[a] = element[b];

element[b] = temp;

}

public int smaller(int a, int b) {

return element[a] < element[b] ? a : b;

}

}

3. 3. 의사 코드

pseudocode

'''procedure''' 힙정렬(a, count) '''is'''

'''input:''' 길이가 ''count''인 정렬되지 않은 배열 ''a''

''(최대값을 루트로 하여 배열 a에 힙을 구축)''

힙화(a, count)

''(다음 루프는 a[0:end−1]이 힙이고''

''end 이후의 모든 요소 a[end:count−1]이 그 앞의 모든 요소보다 크다는''

''불변성을 유지합니다.''

''즉, a[end:count−1]은 정렬된 순서입니다.)''

end ← count

'''while''' end > 1 '''do'''

''(힙 크기는 1씩 감소합니다)''

end ← end − 1

''(a[0]은 루트이자 가장 큰 값입니다. swap은 정렬된 요소 앞으로 이동합니다.)''

swap(a[end], a[0])

''(swap은 힙 속성을 망쳤으므로 복원합니다)''

siftDown(a, 0, end)

''(제자리에서 'a'의 요소를 힙 순서로 넣습니다)''

'''procedure''' 힙화(a, count) '''is'''

''(start는 첫 번째 리프 노드로 초기화됩니다)''

''(0부터 시작하는 배열에서 마지막 요소는 인덱스 count-1에 있습니다. 해당 요소의 부모를 찾습니다)''

start ← iParent(count-1) + 1

'''while''' start > 0 '''do'''

''(마지막 비 힙 노드로 이동)''

start ← start − 1

''(모든 노드가 힙 순서가 되도록 인덱스 'start'의 노드를 적절한 위치로 아래로 이동)''

siftDown(a, start, count)

''(루트를 아래로 이동시킨 후 모든 노드/요소가 힙 순서입니다)''

''(자식에 루트가 있는 힙이 유효하다고 가정하고 인덱스 'start'에 루트 요소가 있는 힙을 복구합니다)''

'''procedure''' siftDown(a, root, end) '''is'''

'''while''' iLeftChild(root) < end '''do''' ''(루트에 자식이 하나 이상 있는 동안)''

child ← iLeftChild(root) ''(루트의 왼쪽 자식)''

''(오른쪽 자식이 있고 해당 자식이 더 크면)''

'''if''' child+1 < end '''and''' a[child] < a[child+1] '''then'''

child ← child + 1

'''if''' a[root] < a[child] '''then'''

swap(a[root], a[child])

root ← child ''(자식을 계속 아래로 이동하려면 반복)''

'''else'''

''(루트는 가장 큰 요소를 포함합니다. 자식에 루트가 있는 힙이 유효하다고 가정할 수 있으므로 완료되었음을 의미합니다.)''

'''return'''

4. 다른 정렬 알고리즘과의 비교

힙 정렬은 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)과 같은 다른 정렬 알고리즘과 비교하여 몇 가지 장단점을 가진다. 힙 정렬은 안정 정렬이 아니다. 즉, 동일한 키 값을 가진 요소들의 상대적인 순서가 정렬 후에도 유지되지 않을 수 있다.

퀵 정렬은 평균적으로 힙 정렬보다 2~3배 빠르지만, 최악의 경우에는 O(n²)의 시간 복잡도를 가질 수 있다. 반면 힙 정렬은 항상 O(n log n)의 시간 복잡도를 보장한다.

병합 정렬은 안정 정렬이지만, 제자리 정렬(in-place sort)이 아니기 때문에 추가적인 메모리 공간이 필요하다. 힙 정렬은 제자리 정렬이므로 추가적인 메모리 공간을 거의 필요로 하지 않는다.

바텀업(Bottom-up) 힙 정렬은 비교 횟수를 줄인 힙 정렬의 변형이다. 일반적인 "탑다운" 힙 정렬이 최악의 경우 및 평균적으로 2n log₂n + O(n) 번의 비교를 필요로 하는 반면, 바텀업 변형은 평균적으로 n log₂n + O(1) 번, 최악의 경우 1.5n log₂n + O(n) 번의 비교를 필요로 한다.[9][10] 비교 연산이 복잡한 경우 (예: 함수 호출을 사용하는 경우) 바텀업 힙 정렬이 유리할 수 있다.

5. 특징

힙 정렬은 데이터의 출현 순서에 따른 계산량 변화가 작다는 특징이 있다. 퀵 정렬의 경우 최악의 상황에서는 O(n^2)의 계산량이 필요하지만, 힙 정렬은 그렇지 않다.[35] 다만, 평균적인 속도는 퀵 정렬보다 느리다.[35] 힙 정렬은 정렬 대상 데이터 자체 외에 추가로 필요한 작업 영역의 크기가 고정되어 있으며, 데이터 양에 영향을 받지 않는다.

하지만 현대 컴퓨터에서 사용되는 고속화 기법에는 적합하지 않은 다음과 같은 특징이 있어 주의해야 한다.


  • 병렬 처리가 불가능하다.
  • 힙 구조는 메모리 접근이 연속적이지 않고 임의 접근이 이루어지므로 공간적 지역성이 낮다.

6. 예시

Heap sort|힙 정렬영어의 예시는 다음과 같다. 정렬하고 싶은 리스트 { 6, 5, 3, 1, 8, 7, 2, 4 }가 있다고 가정한다.

style="text-align: left;" | 1. 힙 만들기
힙새로 추가된 요소요소 교체
null6
65
6, 53
6, 5, 31
6, 5, 3, 18
6, 5, 3, 1, 85, 8
6, 8, 3, 1, 56, 8
8, 6, 3, 1, 57
8, 6, 3, 1, 5, 73, 7
8, 6, 7, 1, 5, 32
8, 6, 7, 1, 5, 3, 24
8, 6, 7, 1, 5, 3, 2, 41, 4
8, 6, 7, 4, 5, 3, 2, 1



style="text-align: left;" | 2. 정렬
힙요소 교체요소 삭제요소 정렬
8, 6, 7, 4, 5, 3, 2, 18, 1
1, 6, 7, 4, 5, 3, 2, 88
1, 6, 7, 4, 5, 3, 21, 78
7, 6, 1, 4, 5, 3, 21, 38
7, 6, 3, 4, 5, 1, 27, 28
2, 6, 3, 4, 5, 1, 778
2, 6, 3, 4, 5, 12, 67, 8
6, 2, 3, 4, 5, 12, 57, 8
6, 5, 3, 4, 2, 16, 17, 8
1, 5, 3, 4, 2, 667, 8
1, 5, 3, 4, 21, 56, 7, 8
5, 1, 3, 4, 21, 46, 7, 8
5, 4, 3, 1, 25, 26, 7, 8
2, 4, 3, 1, 556, 7, 8
2, 4, 3, 12, 45, 6, 7, 8
4, 2, 3, 14, 15, 6, 7, 8
1, 2, 3, 445, 6, 7, 8
1, 2, 31, 34, 5, 6, 7, 8
3, 2, 13, 14, 5, 6, 7, 8
1, 2, 334, 5, 6, 7, 8
1, 21, 23, 4, 5, 6, 7, 8
2, 12, 13, 4, 5, 6, 7, 8
1, 223, 4, 5, 6, 7, 8
112, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8


참조

[1] 논문 On the Best Case of Heapsort https://www.math.cmu[...]
[2] 간행물 The Best Case of Heapsort https://www.cs.princ[...] 1990-10
[3] 서적 The Algorithm Design Manual Springer
[4] 문서 Williams 1964
[5] 서적 Advanced Data Structures Cambridge University Press
[6] 논문 Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
[7] 간행물 A Complete Worst-Case Analysis of Heapsort with Experimental Verification of Its Results, A manuscript 2015-04-07
[8] 문서 Knuth 1997
[9] 웹사이트 Heapsort, Quicksort, and Entropy https://inference.or[...] 2005-12
[10] 논문 A tight lower bound for the worst case of Bottom-Up-Heapsort http://staff.gutech.[...] 1994-02
[11] 서적 Algorithms from P to NP Volume 1: Design and Efficiency Benjamin/Cummings
[12] 서적 Algorithms and Data Structures: The Basic Toolbox http://people.mpi-in[...] Springer
[13] 논문 A variant of heapsort with almost optimal number of comparisons https://pdfs.semanti[...] 1987-03
[14] 논문 Building heaps fast http://cgm.cs.mcgill[...] 1989-09
[15] 논문 The worst case complexity of McDiarmid and Reed's variant of Bottom-Up Heapsort is less than ''n'' log ''n'' + 1.1''n'' 1992-03
[16] 서적 Data Structures Using Pascal Prentice-Hall
[17] 논문 Performance Engineering Case Study: Heap Construction http://hjemmesider.d[...] 2000
[18] 간행물 Mathematical Foundations of Computer Science 2012 2012-08-27–31
[19] 간행물 QuickHeapsort, an efficient mix of classical sorting algorithms https://archive.org/[...] 2000-03-01–03
[20] 논문 QuickHeapsort, an efficient mix of classical sorting algorithms https://core.ac.uk/d[...] 2002-08
[21] 논문 QuickHeapsort: Modifications and improved analysis 2016-08
[22] 문서 Smoothsort – an alternative to sorting in situ
[23] 서적 WADS '89: Proceedings of the Workshop on Algorithms and Data Structures Springer-Verlag
[24] 웹사이트 CartesianTreeSort.hh http://www.keithschw[...] 2010-12-27
[25] 간행물 Seeking for the best priority queue: Lessons learnt http://hjemmesider.d[...] 2013-09-23
[26] 간행물 The Ultimate Heapsort http://hjemmesider.d[...] 1998-02-02–03
[27] 간행물 Pattern-defeating Quicksort 2021-06-09
[27] 웹사이트 pdqsort https://github.com/o[...]
[28] Lecture notes Comparing Quick and Heap Sorts https://www.cs.auckl[...] University of Western Australia
[29] 문서 Linux kernel source https://git.kernel.o[...]
[30] 논문 The Influence of Caches on the Performance of Sorting https://www.cs.auckl[...] 1999-04
[31] 웹사이트 Sorting by generating the sorting permutation, and the effect of caching on sorting https://www.research[...] 2014-05-14
[32] 논문 BlockQuicksort: Avoiding Branch Mispredictions in Quicksort https://drops.dagstu[...] 2019-01-30
[33] 간행물 Simple and Fast BlockQuicksort using Lomuto’s Partitioning Scheme https://epubs.siam.o[...] 2019-01-07–08
[34] 문서 https://doi.org/10.1[...]
[35] 서적 C言語による最新アルゴリズム事典 기술평론사
[36] 서적
[37] 서적 Advanced Data Structures https://archive.org/[...] Cambridge University Press


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com